#include<stdio.h>

int main() {
	int t, n, count;
    
	scanf("%d", &t);
    for(int k = 1; k < t + 1; k++){
        scanf("%d", &n);
        int isprime[n+1];
        count = 0;
        
        for(int i = 0; i < n + 1; i++){
                isprime[i] = 1;
            }
        isprime[0] = isprime[1] = 0;
        
        for(int i = 2; i < n + 1; i++){
            if(isprime[i]){
                count++;
                for(int j = 2; i * j < n + 1; j++)
                    isprime[i * j] = 0;
            }
        }
        printf("%d\n", count);
    }
    
   
	return 0;
}
/*链接：https://ac.nowcoder.com/acm/problem/22226
来源：牛客网

质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
例如小于10的质数有2，3，5，7。
输入描述:
第一行输入一个整数T，表示询问的个数

接下来T行每行输入一个整数n.

1<=T<=1e8,1<=n<=1000000
*/